#include <stdio.h>   // 提供输入输出相关的函数，如 printf、fgets
#include <string.h>  // 提供字符串处理相关的函数，如 strlen、strcspn

// step 1# 定义函数 findRedundantCover，查找满足条件的子串起始位置
int findRedundantCover(const char *s1, const char *s2, int k);

int main() {
    // step 2# 读取输入字符串 s1 和 s2
    char s1[1000], s2[1000];
    fgets(s1, 1000, stdin);  // 读取整行字符串 s1
    fgets(s2, 1000, stdin);  // 读取整行字符串 s2
    
    // step 3# 读取整数 k
    int k;
    scanf("%d", &k);  // 读取整数 k

    // step 4# 去除换行符
    s1[strcspn(s1, "\n")] = '\0';  // 去除 s1 末尾的换行符
    s2[strcspn(s2, "\n")] = '\0';  // 去除 s2 末尾的换行符

    // step 5# 调用查找函数并输出结果
    printf("%d\n", findRedundantCover(s1, s2, k));  // 输出查找结果

    return 0;
}

// step 6# 定义查找重复覆盖函数 findRedundantCover
int findRedundantCover(const char *s1, const char *s2, int k) {
    // step 7# 计算 s1 中每个字符的出现次数
    int s1Count[26] = {0};  // 创建一个长度为26的数组，用于记录每个字母的出现次数
    for (int i = 0; s1[i] != '\0'; i++) {
        s1Count[s1[i] - 'a']++;  // 计算每个字符在 s1 中的出现次数
    }

    // step 8# 初始化滑动窗口的左右边界、剩余需要匹配的 s1 字符数和窗口内字符计数数组
    int left = 0, right = 0;  // 左右滑动窗口边界
    int s1CharsLeft = strlen(s1);  // 剩余需要匹配的字符数
    int windowCount[26] = {0};  // 初始化滑动窗口中每个字母的出现次数数组

    // step 9# 遍历 s2 字符串，调整窗口大小
    while (s2[right] != '\0') {
        // step 10# 将右边界字符加入窗口计数
        char rightChar = s2[right];
        windowCount[rightChar - 'a']++;  // 增加窗口内该字符的计数

        // step 11# 如果该字符在 s1 中存在且匹配的数量不超过 s1 中的数量，减少剩余需要匹配的字符数
        if (windowCount[rightChar - 'a'] <= s1Count[rightChar - 'a']) {
            s1CharsLeft--;  // 减少剩余需要匹配的字符数
        }

        // step 12# 如果窗口的长度大于 s1 长度 + k，移动左边界
        if (right - left + 1 > strlen(s1) + k) {
            char leftChar = s2[left];
            // step 13# 如果左边界字符在 s1 中存在且数量不超过 s1 中的数量，增加剩余需要匹配的字符数
            if (windowCount[leftChar - 'a'] <= s1Count[leftChar - 'a']) {
                s1CharsLeft++;  // 增加剩余需要匹配的字符数
            }
            // step 14# 将左边界字符从窗口计数中移除
            windowCount[leftChar - 'a']--;
            left++;  // 移动左边界
        }

        // step 15# 如果剩余需要匹配的字符数为0，返回满足条件的子串起始位置
        if (s1CharsLeft == 0) {
            return left;  // 返回满足条件的子串起始位置
        }

        // step 16# 移动右边界
        right++;  // 移动右边界
    }

    // step 17# 如果遍历完 s2 仍未找到满足条件的子串，返回 -1
    return -1;  // 未找到满足条件的子串，返回 -1
}
